package com.wujunshen.algorithm.leetcode.dynamic.programming;

import java.util.Arrays;

/**
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/11 17:15<br>
 */
public class 最长递增子序列 {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        //dp[i] 的值代表 nums 以 nums[i] 结尾的最长子序列长度
        int[] dp = new int[nums.length];
        int result = 0;
        Arrays.fill(dp, 1);

        for (int i = 0; i < nums.length; i++) {
            //当 nums[i] > nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j] + 1 ；
            //当 nums[i] <= nums[j] 时： nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。
            for (int j = 0; j < i; j++) {
                if (  nums[i]>nums[j]) {
                    //转移方程： dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}
